package com.zhugang.week13.stack;

import java.util.Stack;

/**
 * @program algorithms
 * @description: validateStackSequences
 * @author: chanzhugang
 * @create: 2022/11/11 00:05
 */
public class ValidateStackSequences {

    /**
     * 剑指offer 31 栈的压入、弹出序列
     * https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
     *
     * @param pushed
     * @param popped
     * @return
     */
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        /**
         * 双指针i、j分别控制两个数组位置；
         * 栈存储的是pushed数据，栈顶元素和poped元素比较，如果相等弹出栈顶元素，循环继续比较
         */
        int i = 0;
        int j = 0;
        int k = 0;
        Stack<Integer> stack = new Stack<>();
        while (k < pushed.length + popped.length) {
            k++;
            if (!stack.isEmpty() && stack.peek() == popped[j]) {
                // 可以消掉一个元素
                stack.pop();
                j++;
                continue;
            }
            // 入栈
            if (i < pushed.length) {
                stack.push(pushed[i]);
                i++;
                continue;
            }
            //
            return false;
        }
        return true;
    }


    public boolean validateStackSequences2(int[] pushed, int[] popped) {
        /**
         * 推荐：代码更简洁
         * 栈模拟：pushed每个元素入栈；栈不为空且栈顶元素和popped当前元素相同，消除一个; 栈是否能消完？
         */
        Stack<Integer> stack = new Stack<>();
        int n = pushed.length;
        for (int i = 0, j = 0; i < n; i++) {
            stack.push(pushed[i]);
            while (!stack.isEmpty() && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}